
#include"hphiga.h"

 
hphiga::hphiga(long array_size, int max_population_size, int tournament_type, float max_fraction_of_population_selected, int max_participants)
{
	int i;

	//random.randomize(0.345356*(double)rand());
	//random.randomize((int)(rand()*time(NULL)));
	//random.makeSeed();
	
	//initialize the default parameters
	this->initialize();


	this->array_size=array_size;
	this->max_population_size= max_population_size;
	this->tournament_type= tournament_type;
	this->max_fraction_of_population_selected= max_fraction_of_population_selected;
	this->max_participants= max_participants;
	
	
	//allocate variables
	selected_population_size= max_population_size*max_fraction_of_population_selected;

	population= (int **)malloc(sizeof(int*)*max_population_size);
	for(i=0;i<max_population_size;++i)
	{
		population[i]= (int *)malloc(sizeof(int)*array_size);
	}
	
	distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}
	
	tmp_distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		tmp_distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}
	
	//create a temporary population, used to store the best selected individuals of the population
	best_population= (int **)malloc(sizeof(int*)*selected_population_size);
	for(i=0;i<selected_population_size;++i)
	{
		best_population[i]= (int *)malloc(sizeof(int)*array_size);
	}
	
	building_blocks= (int*)malloc(sizeof(int)*array_size);

	
	
}

hphiga::hphiga(const char* filename, int argc, char** argv)
{
	int i;

	//initialize the default parameters
	initialize();

	//read a file with the paremeters to set over
	getParametersFromFile(filename);

	if(argc>1)
	{
		printf("argc: %d\n",argc);
		if(argc==3)
		{
			int new_pop= atoi(argv[1]);
			int new_problem_size= atoi(argv[2]);
			printf("setting population to: %d\n",new_pop);
			setMaxPopulation(new_pop);				
			printf("setting problem size to: %d\n",new_problem_size);
			setProblemSize(new_problem_size);				
		}
		else
		{
			printf("Wrong number of parameters passed\n");
			printf("Usage:\n\t%s population_size problem_size\n",argv[0]);
			exit(1);
		}
	}

	
	//allocate variables
	selected_population_size= max_population_size*max_fraction_of_population_selected;

	population= (int **)malloc(sizeof(int*)*max_population_size);
	
	for(i=0;i<max_population_size;++i)
	{
		population[i]= (int *)malloc(sizeof(int)*array_size);
	}
	
	distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}
	
	tmp_distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		tmp_distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}
	
	//create a temporary population, used to store the best selected individuals of the population
	best_population= (int **)malloc(sizeof(int*)*selected_population_size);
	for(i=0;i<selected_population_size;++i)
	{
		best_population[i]= (int *)malloc(sizeof(int)*array_size);
	}
	
	//allocating BBs
	building_blocks= (int*)malloc(sizeof(int)*array_size);

	printf("ready\n");
}

hphiga::hphiga()
{
	//initialize the default parameters
	initialize();

}

hphiga::~hphiga()
{
	int i;

	for(i=0;i<max_population_size;i++)
	{
		free(population[i]);
	}
	free(population);

	selected_population_size= max_fraction_of_population_selected;	

	for(i=0;i<selected_population_size*2;i++)
	{
		free(best_population[i]);
	}
	free(best_population);
	
	for(i=0;i<array_size;i++)
	{
		free(distance_matrix[i]);
	}
	free(distance_matrix);

}

//initialize every variable
void hphiga::initialize()
{
	//initialize seed for pseudo random numbers
	srand(rand()*time(NULL));
	srandom(time(NULL));
	
	random.randomize(0.345356);
	
	fitness_pointer=NULL;

	generation=1;

	
	use_fast_log=false;

	print_tree=false;

	elitism= false;

	hill_climbing= DO_NOT_APPLY;

	function_k= 1.0;

	mutation_chance=0;

	statistical_bbs=0;

	father_mother=0;

	print_BB=false;
	
	terminal_input=false;

	ending_type= NO_ENDING;

	cccs= NULL;
				
	number_of_layers_with_probability=0;
	
	accumulated_beta_sum= 0.0;

	neighbor_joining_metric= 0;
	
	only_print_neighbor_joining_data=false;
	
	neighbor_joining_repetitions= 1;

	noise_value= 0.0;

	model_build_option= 0;
	
	

}
		
void hphiga::setFactor(float factor)
{
	max_fraction_of_population_selected= factor;
	
}

void hphiga::setProblemSize(int size)
{
	array_size= size;
}

void hphiga::setSeed(int seed)
{
	random.randomize(seed);
}

void hphiga::setTournamentSize(int size)
{
	max_participants= size;
}

void hphiga::allocate()
{
	int i;

	//allocate variables
	selected_population_size= max_population_size*max_fraction_of_population_selected;

	population= (int **)malloc(sizeof(int*)*max_population_size);
	
	for(i=0;i<max_population_size;++i)
	{
		population[i]= (int *)malloc(sizeof(int)*array_size);
	}
	
	distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}
	
	tmp_distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		tmp_distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}
	
	//create a temporary population, used to store the best selected individuals of the population
	best_population= (int **)malloc(sizeof(int*)*selected_population_size);
	for(i=0;i<selected_population_size;++i)
	{
		best_population[i]= (int *)malloc(sizeof(int)*array_size);
	}
	
	//allocating BBs
	building_blocks= (int*)malloc(sizeof(int)*array_size);

}

// Read file to get parameters
void hphiga::getParametersFromFile(const char* filename)
{
	FILE* fp;
	char buffer[512];
	char buffer2[512];
	int parameter;

	fp= fopen(filename,"r");
	if(!fp)
	{
		printf("ERROR: could not open %s\n",filename);
		return;
	}

	while(!feof(fp))
	{
	
		fgets(buffer, sizeof(buffer), fp);

		if(sscanf(buffer,"population %d",&parameter) == 1)
		{
			printf("population %d\n",parameter);
			max_population_size= parameter;
			
		}
		else if(sscanf(buffer,"factor %f",&max_fraction_of_population_selected) == 1)
		{
			printf("fraction %f\n", max_fraction_of_population_selected);
		}
		else if(sscanf(buffer,"problem_size %ld",&array_size) == 1)
		{
			printf("problem size %ld\n",array_size);
		}
		else if(sscanf(buffer,"tournament_size %d",&max_participants) == 1)
		{
			printf("tournament size %d\n",max_participants);
		}
		else if(sscanf(buffer,"tournament_type %s",&buffer2) == 1)
		{
			
			if(!strcmp(buffer2,"exclusive"))
			{
				tournament_type= EXCLUSIVE_TOURNAMENT;	
				
				printf("tournament_type %s\n",buffer2);
			}
			else
			{
				tournament_type= SIMPLE_TOURNAMENT;	
				
				printf("tournament_type %s\n",buffer2);
			}
		}
		else if(sscanf(buffer,"problem_type %d",&parameter) == 1)
		{
			switch(parameter)
			{
				case 0:
					setFitnessFunction(&onemax);
					printf("onemax\n");
				break;
				case 1:
					setFitnessFunction(&fdeception);
					printf("fdeception\n");
				break;
				case 2:
					setFitnessFunction(&quadratic);
					printf("quadratic\n");
				break;
				case 3:
					setFitnessFunction(&f3deceptiveOverlapping);
				break;
				case 4:
					setFitnessFunction(&f3deceptive);
				break;
				case 5:
					setFitnessFunction(&trap5);
				break;
				case 6:
					setFitnessFunction(&f3deceptiveBipolar);
				break;
				case 7:
					setFitnessFunction(&trap5_cyclic);
					printf("Trap5 Cyclic\n");
				break;
				case 8:
					setFitnessFunction(&password2);
					printf("Trap5 Cyclic\n");
				break;
				default:
					printf("ERROR: no fitness set\n");
					exit(1);
				break;
			}
		}
		else if(sscanf(buffer,"neighbor_joining_repetitions %d",&neighbor_joining_repetitions) == 1)
		{
		}
		else if(sscanf(buffer,"model_build_option %d",&model_build_option) == 1)
		{
		}
		else if(sscanf(buffer,"cut_metric %d",&cut_metric) == 1)
		{
		}
		else if(sscanf(buffer,"build_metric %d",&build_metric) == 1)
		{
		}
		else if(sscanf(buffer,"neighbor_joining_metric %d",&neighbor_joining_metric) == 1)
		{
		}
		else if(!strncmp(buffer,"only_print_neighbor_joining_data",32))
		{
			only_print_neighbor_joining_data=true;
		}
		else if(!strncmp(buffer,"print_tree_each_generation",26))
		{
			print_tree=true;
		}
		else if(!strncmp(buffer,"terminal_input",14))
		{
			terminal_input=true;
		}
		else if(sscanf(buffer,"noise_value %f",&noise_value) == 1)
		{
			printf("noise %f\n",noise_value);
		}


	}

	fclose(fp);

}

void hphiga::setNeighborJoiningMetric(int metric)
{
	this->neighbor_joining_metric= metric;
}

void hphiga::enableElitism()
{
	elitism= true;
}

void hphiga::setFatherMother()
{
	father_mother=1;
}

void hphiga::enableHillClimbing(float chance_of_hill_climbing, int apply_hill_climbing)
{
	hill_climbing= apply_hill_climbing;

	this->chance_of_hill_climbing= chance_of_hill_climbing;
}

void hphiga::enablePrintTreeEachGeneration()
{
	print_tree= true;
}

void hphiga::onlyPrintNeighborJoiningData()
{
	only_print_neighbor_joining_data=true;
}

void hphiga::setMetric(int build_metric, int cut_metric)
{
	this->build_metric=build_metric;
	
	this->cut_metric=cut_metric;

	if(cut_metric==LAYER_CUT_FUNCTION)
	{
		free(building_blocks);
		statistical_bbs=1;
		number_of_layers_with_probability=0;
		accumulated_beta_sum= 0.0;
	}
}

void hphiga::setMutation(int percent)
{
	mutation_chance= percent;
}

void hphiga::computeCCCs()
{
	compute_cccs=true;
}

void hphiga::computeAndPrintCCCs()
{
	compute_cccs=true;
	print_cccs=true;
}

void hphiga::setModelBuildOption(int option)
{
	model_build_option=option;
}

void hphiga::setLayersProbability(float* layers_probability, int number_of_layers)
{
	int i;

	this->number_of_layers_with_probability= number_of_layers;
	this->layers_probability= (float*)malloc(number_of_layers*sizeof(float));

	for(i=0; i<number_of_layers; i++)
	{
		this->layers_probability[i]= layers_probability[i];
	}
}

void hphiga::enableFastLog()
{
	printf("Caching Values for fast log...\n");
	prepare_log(100000000);

	use_fast_log=true;
}

void hphiga::setFitnessFunction(float (*fitness_pointer)(int* chromossome, int generation, long array_size))
{
	this->fitness_pointer= *fitness_pointer;
}

float hphiga::testFitness(int *chromossome, int generation, long array_size)
{
	return  (*fitness_pointer)(chromossome, 0, array_size);
}

void hphiga::setEnding(int ending_type, int (*ending_function)(int** possible_building_blocks, int* blocks, int array_size, float* cccs, int number_of_bbs))
{
	this->ending_type= ending_type;
	this->ending_function= *ending_function;
}

void hphiga::setNoise(float noise)
{
	noise_value= noise;
}

void hphiga::setNeighborJoiningRepetitions(int repetitions)
{
	neighbor_joining_repetitions= repetitions;
}

void hphiga::setK(float k)
{
	function_k= k;
}

void hphiga::oldVariation(int population_size)
{
		
	Graph_Node* tree;
	list<int> node_to_cut_list;

	switch(model_build_option)
	{
		//build also the matrix for the worst
		case 1:
		{
			int tmp_build_metric= build_metric;

			//set new metric
			build_metric= MUTUAL_INFORMATION_ONLY_WORST;

			buildDistanceMatrix(population_size);

			//restore original metric 
			build_metric= tmp_build_metric;

		
			//create the tree 
			tree= neighborJoining(distance_matrix, array_size, &node_to_cut, neighbor_joining_metric);
			
			printf("node to cut (worst) %d\n",node_to_cut);
		
			node_to_cut_list.push_back(node_to_cut);

				
		}
		break;
		
		//build also the matrix for the worst summed with the best
		case 2:
		{
			int tmp_build_metric= build_metric;

			//set new metric
			build_metric= MUTUAL_INFORMATION_WORST_PLUS_BEST;

			buildDistanceMatrix(population_size);

			//restore original metric 
			build_metric= tmp_build_metric;

		
			//create the tree 
			tree= neighborJoining(distance_matrix, array_size, &node_to_cut, neighbor_joining_metric);
			
			printf("node to cut (worst+best) %d\n",node_to_cut);
		
			node_to_cut_list.push_back(node_to_cut);
			
		}
		break;
		
		//build also the matrices for: the worst summed with the best, the worst. 
		//And store their respective node_to_cut in the node_to_cut_list
		case 3:
		{
			int tmp_build_metric= build_metric;

			//set new metric
			build_metric= MUTUAL_INFORMATION_WORST_PLUS_BEST;

			buildDistanceMatrix(population_size);

			//create the tree 
			tree= neighborJoining(distance_matrix, array_size, &node_to_cut, neighbor_joining_metric);
		
			printf("node to cut (worst+best) %d\n",node_to_cut);

			node_to_cut_list.push_back(node_to_cut);
		

			//set new metric
			build_metric= MUTUAL_INFORMATION_ONLY_WORST;

			buildDistanceMatrix(population_size);

			//restore original metric 
			build_metric= tmp_build_metric;

			//create the tree 
			tree= neighborJoining(distance_matrix, array_size, &node_to_cut, neighbor_joining_metric);
			
			printf("node to cut (worst) %d\n",node_to_cut);
		
			node_to_cut_list.push_back(node_to_cut);
		}
		break;

	}
}

void hphiga::setMaxPopulation(int pop)
{
	max_population_size= pop;
}

void hphiga::createRandomPopulation(int population_size)
{
	int i,j;

	//create random population
	for(i=0;i<population_size;++i)
	{
		for(j=0;j<array_size;++j)
		{
			//if(((double)rand()/((double)RAND_MAX + (double)1.0f))>0.49)
			//if(random()%2)
			if(random.uniform(0.0,1.0)>0.49)
			{
				population[i][j]=1;
			}
			else
			{
				population[i][j]=0;
			}
		}
	}
}
		

void hphiga::createNextPopulation(int population_size)
{
	int i,j;

	if(elitism)
	{
		int k;
		for(k=0; k<array_size;k++)
		{
			population[0][k]= best_individual[k];	
		}
				
		//hillClimbing(population[0]);
				
		//generate only the next individuals not the first one
		i=1;
	}
	else
	{
		//generate all population
		i=0;
	}
	
	//create population based on crossing over of the last, using the last building blocks
	for(;i<population_size;i++)
	{
		if(statistical_bbs==1)
		{

			//printf("max %d choose %d\n",number_of_bbs, choose_bb);

			//do a roulette to choose a layer, based on the probability passed
			if(number_of_layers_with_probability!=0)
			{
				float roulette_number= random.uniform(0.0,1.0)*accumulated_beta_sum;

				int k;
				//check if the probability of this layer falls between the low and high limits
				float high_limit=0;
				for(k=0;k<number_of_layers_with_probability;k++)
				{
					high_limit+= layers_probability[k]; 
					//printf("aaa %.2f prob %.2f\n", high_limit, roulette_number);
					if(roulette_number<high_limit)
					{

						int choose_bb=k;
						/*
						if(k>=number_of_bbs)
						{
							choose_bb= random.uniform(0,number_of_bbs-1);
						}
						else
						{
							choose_bb= k;

						}*/

						building_blocks= possible_building_blocks[choose_bb];
						blocks= possible_blocks[choose_bb];
						
						//printf("max %d choose %d\n",number_of_bbs, choose_bb);
						
						break;
					}
				}
			
			}
			else
			{	
				int choose_bb= random.uniform(0,number_of_bbs-1);

				building_blocks= possible_building_blocks[choose_bb];
				blocks= possible_blocks[choose_bb];
			}
		}
		
		if(father_mother==1)
		{
			//choosing the father and mother
			int father= (int)trunc(random.uniform(0,selected_population_size-1));
			
			int mother= (int)trunc(random.uniform(0,selected_population_size-1));
			
			//make sure they are different
			while(father==mother)
			{
				mother= (int)trunc(random.uniform(0,selected_population_size-1));
			}
			
			//mother= 0
			//father= 1
			for(j=0;j<blocks;++j)
			{
				int k;

				//vaiable that defines if the gene block will come from the mother or father
				float gene_inheritance= random.uniform(0,1);

				for(k=0; k<array_size;k++)
				{
					//check if this gene if from the respective building block that we are
					if( building_blocks[k]==j)
					{
						if(gene_inheritance>0.49)
						{
							population[i][k]=best_population[mother][k];
						}
						else
						{
							population[i][k]=best_population[father][k];
						}
					}
				}
			}
		}
		else
		{
			//there is no mother or father, the building block could comes from anybody in the population
			//so for each building block, selects a chromossome and generates the genetic part for the 
			//offspring
			for(j=0;j<blocks;++j)
			{
				int k;

				//vaiable that defines from which chromossome the building block will come
				int gene_inheritance= random.uniform(0,selected_population_size-1);

				for(k=0; k<array_size;k++)
				{
					//check if this gene is from the respective building block that we are
					if(building_blocks[k]==j)
					{
						population[i][k]=best_population[gene_inheritance][k];
					}

				}
			}
		}

		if(hill_climbing==NEW_POPULATION)
		{
			//compute the chance of ocurring hill climbing
			if(random.uniform(0.0,1.0) < chance_of_hill_climbing)
			{
				hillClimbing(population[i]);
			}
		}
		
	}
	
	/*
	//free last possible bbs
	if(statistical_bbs==1)
	{
		for(i=0;i<number_of_bbs;i++)
		{
			free(possible_building_blocks[i]);
		}
		free(possible_building_blocks);
		
		free(possible_blocks);
	}
	*/

				
	if(mutation_chance>0)
	{
		int k;
		for(i=0;i<population_size;i++)
		{
			for(k=0; k<array_size;k++)
			{
				float chance= random.uniform(0,100);
				if(mutation_chance> chance)
				{
					if(population[i][k]==0)
					{
						population[i][k]=1;
					}
					else
					{
						population[i][k]=0;
					}
				}
			}
		}
		
	}
}

void hphiga::populationSelection(int population_size)
{
	int i,j;

	int* selected_index_array;
	if(tournament_type==EXCLUSIVE_TOURNAMENT)
	{
		selected_index_array=(int*)malloc(sizeof(int)*selected_population_size);
	}

	for(i=0;i<selected_population_size;++i)
	{
		long champion_index;

		switch(tournament_type)
		{
			case SIMPLE_TOURNAMENT:
			{
				//receive the index of the tournament's champion
				champion_index= simple_tournament(max_participants, population_size);
			}
			break;

			case EXCLUSIVE_TOURNAMENT:
			{
				//receive the index of the tournament's champion
				champion_index= exclusive_tournament(max_participants, population_size, i, selected_index_array);
				//printArray(selected_index_array, i);
			}
			break;

		}

		for(j=0;j<array_size;++j)
		{
		
			best_population[i][j]= population[champion_index][j];
		
		}
			
		if(hill_climbing==SELECTED_POPULATION)
		{
			//compute the chance of ocurring hill climbing
			if(random.uniform(0.0,1.0) < chance_of_hill_climbing)
			{
				hillClimbing(best_population[i]);
			}
		}
	}
	
	if(tournament_type==EXCLUSIVE_TOURNAMENT)
	{
		//printArray(selected_index_array, selected_population_size);
		free(selected_index_array);
	}

}

bool hphiga::evolve(int population_size, float* fitness_result)
{
	int i,j;

	printf("\nGeneration %d\n", generation);
	
	if(fitness_pointer==NULL)
	{
		printf("ERROR: No fitness function defined and passed to setFitnessFuction().\n");
		exit(1);
	}

	if(population_size<=0)
	{
		population_size=max_population_size;
	}

	if(population_size>max_population_size)
	{
		printf("ERROR: population set for this evolution is greater than the maximum population\n.");
		printf("Ignored\n");

		population_size=max_population_size;
	}
	
	//set the size of the population size
	selected_population_size= max_fraction_of_population_selected*population_size;


	/********** Create Population **************/
	
	//if first generation
	if(generation==1)
	{
		createRandomPopulation(population_size);
	}
	else
	{
		createNextPopulation(population_size);
	}
	

	/***** Selection *******/

	populationSelection(population_size);

	/********* Create Model  *************/

	
	if(generation==1)
	{
		
		Graph_Node* tree;
		list<int> node_to_cut_list;
		int answer_without_noise= -1;

		//oldVariation(population_size);

		//use a metric to compute the similarity of variables and create the distance matrix
		buildDistanceMatrix(population_size);

		float avg=0;
		float counter=0;
			
		//store the matrix for later 
		for(i=0;i<array_size;i++)
		{
			for(j=i+1;j<array_size;j++)
			{
				tmp_distance_matrix[j][i]= distance_matrix[j][i];
				
				avg+= distance_matrix[j][i];
				counter++;
				//printf("distance %f \n", distance_matrix[j][i]);
			}
		}
		
		//calculate average;
		avg= avg/counter;
			
		float variance = 0;

		float noise;

		if(noise_value==0)
		{
			
			//compute variance
			for(i=0;i<array_size;i++)
			{
				for(j=i+1;j<array_size;j++)
				{
					//printf("distance %f   %f\n", avg, distance_matrix[j][i]);
					float var= (distance_matrix[j][i] - avg)*(distance_matrix[j][i] - avg);
					variance+= var;
					//printf("variance %f   %f\n", var, variance);
				}
				
			}

			variance= variance/counter;

			variance= sqrt(variance);
		

			noise= variance/2; //noise_value;//(int)tmp_distance_matrix[1][0]/2;
		
			printf("noise %f  distance %f avg %f  variance %f\n",noise, tmp_distance_matrix[1][0], avg, variance);
		}
		else
		{
			noise= noise_value;
			
			printf("noise %f  distance %f avg %f\n",noise, tmp_distance_matrix[1][0], avg);
		}
		
		//printMatrix(tmp_distance_matrix,array_size);
		
		
		//create some different trees by adding noise to the matrix 
		int k;
		for(k=0; k<neighbor_joining_repetitions; ++k)
		{

			//node_to_cut ( every number >= to this node number must be cutted out of the tree)
			//create the tree 
			printf("metric %d\n",neighbor_joining_metric);
			
		
			if(k==0)
			{
				tree= neighborJoining(distance_matrix, array_size, &node_to_cut, neighbor_joining_metric, &beta, &beta_size);
				//return false;
			}
			else
			{
				tree= neighborJoining(distance_matrix, array_size, &node_to_cut, neighbor_joining_metric);
			}

			//printArray(beta, beta_size);

			//include noise
			for(i=0;i<array_size;i++)
			{
				for(j=0;j<array_size;j++)
					distance_matrix[i][j]= tmp_distance_matrix[i][j] + random.uniform((-noise/2.0f),(noise/2.0f));
			}

			//store the first node_to_cut in the answer_without_noise, because this result is more precise than the others
			if(k==0)
			{
				answer_without_noise= node_to_cut;
			}

			node_to_cut_list.push_back(node_to_cut);
				
		}

		node_to_cut_list.sort();

		int best_node=-1;
		int best_count=-1;

		int i_node=-1;
		int i_count=0;

		//decide which of the cut_nodes in the node_to_cut_list to use to cut the tree
		list<int>::iterator ite;
		for(ite=node_to_cut_list.begin() ; ite!=node_to_cut_list.end() ; ite++)
		{
			//printf("node %d\n", (*ite));
			
			

			if(i_node == -1)
			{
				//initializing the countage for a node
				i_node=(*ite);

				if(i_node==answer_without_noise)
					i_count=1;
				else
					i_count=0;
			}
			else
			{
				if(i_node == (*ite))
				{
					i_count++;
				}
				//i_node != (*ite)
				else
				{
					printf("node %d count %d\n",i_node, i_count);

					if(i_count>best_count)
					{
						best_node= i_node;
						best_count= i_count;
					}
					
					//initializing the countage for another node
					i_node=(*ite);

					if(i_node==answer_without_noise)
						i_count=1;
					else
						i_count=0;

				}
			}


		}
		
		printf("node %d count %d\n",i_node, i_count);
		//test the last node
		if(i_count>best_count)
		{
			best_node= i_node;
			best_count= i_count;
		}
			
		printf("first node %d\n", answer_without_noise);
		printf("\nchoice node: %d\n", best_node);
		printf("accuracy (1 - 6): %d\n", best_count);

		node_to_cut= best_node;

		printArray(beta, beta_size);
			
		if(print_tree)
		{
			tree->print();
		}


		if(only_print_neighbor_joining_data)
		{
			exit(1);
		}

		//tree->print();

		bool exit= false;
	
		//------------------creating the building blocks to solve the linkage learning  ----------------------------------/
		number_of_bbs=beta_size;

		possible_building_blocks=(int**)malloc(sizeof(int*)*(number_of_bbs));
		for(i=0;i<number_of_bbs;i++)
		{
			possible_building_blocks[i]=(int*)malloc(sizeof(int)*array_size);
		}
		
		possible_blocks=(int*)malloc(sizeof(int)*(number_of_bbs));

		//use a metric to create the building blocks based on cutting the tree structure
		float fitness=cutTree(tree, number_of_bbs, node_to_cut);

//		printf("exit %d ending %d\n",exit, ending_type);
			
//		*fitness_result= fitness;
//		best_fit= fitness;
//		return false;

		/*if(exit==true)
		{
			*fitness_result= fitness;
			best_fit= fitness;
			return false;
		}*/

		/*switch(ending_type)
		{
			case NO_ENDING:
				break;
			case FUNCTION:
				{
					int chosen_bb=(*ending_function)(possible_building_blocks, possible_blocks, array_size, cccs, number_of_bbs);	
					
					//int* building_block= possible_building_blocks[chosen_bb];
					//int blocks= possible_blocks[chosen_bb];
					int* best_solution;
					float best_fitness;

					best_solution= generateAllPossibilities(possible_building_blocks[chosen_bb], possible_blocks[chosen_bb]);
					best_fitness= (*fitness_pointer)(best_solution, 0, array_size);
					
					`printf("\nbest fitness: %.2f\n",best_fitness);
					printArray(best_solution, array_size);

					*fitness_result= best_fitness;
					best_fit= best_fitness;

					return false;
					

				}
				break;
			default:
				break;
		}
		*/
	}


	printBBs();

	generation++;


	//return true;
	return checkStopCondition(population_size);
	
}
	
void hphiga::printBBs()
{
	int i;

	//printing building blocks
	if(print_BB==true)
	{
		printf("building block: ");	
		for(i=0;i<array_size;i++)
		{
			printf(" %d",building_blocks[i]);	
		}
		printf("\n");	
	}
}

//use a cut metric to build Building blocks from a tree of distances
//return the fitness if the exit boolean is true,
//meaning that the cutting algorithm already found the solution
float hphiga::cutTree(Graph_Node* tree, int number_of_bbs, int cut_node)
{
	int i;

	printf("printinf BBs  %d\n\n",cut_node);

	for(i=0;i<number_of_bbs;i++)
	{
		possible_blocks[i]= applyDiscontinuityFunction(tree, possible_building_blocks[i], array_size + i);
		printf("beta %.2f\n",beta[i]);
		printArray(possible_building_blocks[i], array_size); 
	}
	
	this->number_of_layers_with_probability= number_of_bbs;
	this->layers_probability= (float*)malloc(number_of_bbs*sizeof(float));

	float count=0;

	for(i=0; i<number_of_layers_with_probability; i++)
	{
		this->layers_probability[i]= beta[i];
		count+= beta[i];
	}

	accumulated_beta_sum= count;
	printf("accumulated %f\n",accumulated_beta_sum);

	statistical_bbs=1;
	

	/*
	 *  EXHAUSTIVE SEARCH
	 *
	int* best_solution;
	float best_fitness;

	best_solution= generateAllPossibilities(building_blocks, blocks);
	best_fitness= (*fitness_pointer)(best_solution, 0, array_size);
	
	printf("\nbuilding blocks: %.2f\n",best_fitness);
	printArray(building_blocks, array_size);
	printArray(best_solution, array_size);
	printf("bestfitness: %.2f\n",best_fitness);

	//exit(1);
	//return false;// false;
	*exit= true;
	return best_fitness;
	*/

	return 0;
}

void hphiga::buildDistanceMatrix(int population_size)
{

	switch(build_metric)
	{
		case MIX_METRIC:
		{
			mixMetric(best_population, selected_population_size, array_size);
		}
		break;
		
		case AVERAGE_VALUE:
		{
			valueMetric(best_population,selected_population_size,array_size);

		}
		break;

		case MUTUAL_INFORMATION:
		{
			binaryMutualInformationMetric(best_population, selected_population_size, array_size);

		}
		break;
		
		case MUTUAL_INFORMATION_ONLY_WORST:
		{
			int i,j;
			
			//it will hold the best population in the best_population array, but will create 
			//the distance matrix based on the worst population
			
			int ** worst_population= (int **)malloc(sizeof(int*)*selected_population_size);
			for(i=0;i<selected_population_size;++i)
			{
				worst_population[i]= (int *)malloc(sizeof(int)*array_size);
			}
	
			for(i=0;i<selected_population_size;++i)
			{
				long champion_index;

				switch(tournament_type)
				{
					case SIMPLE_TOURNAMENT:
					{
						//receive the index of the tournament's champion
						champion_index= loser_of_the_simple_tournament(max_participants, population_size);
					}
					break;

					case EXCLUSIVE_TOURNAMENT:
					{
						//receive the index of the tournament's champion
						//champion_index= loser_of_the_exclusive_tournament(max_participants, population_size, i, selected_index_array);
						//printArray(selected_index_array, i);
						printf("Just remind you are using exclusive tournament with mutual information only worst, something can goes wrong!\nThis option was not entirely programmed\n");
					}
					break;

				}

				for(j=0;j<array_size;++j)
				{
				
					worst_population[i][j]= population[champion_index][j];
				
				}
					
			}


			binaryMutualInformationMetric(worst_population, selected_population_size, array_size);
			
			for(i=0;i<selected_population_size;++i)
			{
				free(worst_population[i]);
			}
			free(worst_population);

		}
		break;
		
		case MUTUAL_INFORMATION_ONLY_BEST:
		{
			binaryMutualInformationMetric(best_population, selected_population_size, array_size);

		}
		break;
	
		/*
		case MUTUAL_INFORMATION_WORST_PLUS_BEST:
		{
			int i,j;
			
			//it will hold the best population in the best_population array, but will create 
			//the distance matrix based on the worst population

			//selected_population_size= selected_population_size*2;
			
			//for(i=0;i<selected_population_size;++i)
			//{
			//	best_population[i]= (int *)malloc(sizeof(int)*array_size);
			//}

			
	
			for(i=(selected_population_size/2); i<selected_population_size ; ++i)
			{
				long champion_index;

				switch(tournament_type)
				{
					case SIMPLE_TOURNAMENT:
					{
						//receive the index of the tournament's champion
						champion_index= loser_of_the_simple_tournament(max_participants, population_size);
					}
					break;

					case EXCLUSIVE_TOURNAMENT:
					{
						//receive the index of the tournament's champion
						//champion_index= loser_of_the_exclusive_tournament(max_participants, population_size, i, selected_index_array);
						//printArray(selected_index_array, i);
						printf("Just remind you are using exclusive tournament with mutual information best plus worst, something can goes wrong!\nThis option was not entirely programmed\n");
					}
					break;

				}

				for(j=0;j<array_size;++j)
				{
				
					best_population[i][j]= population[champion_index][j];
				
				}
					
			}


			binaryMutualInformationMetric(best_population, selected_population_size, array_size);
			
		
			//restauring the real selected_population_size, modified for the calculation of a better distance matrix
			selected_population_size= selected_population_size/2;

		}
		break;
		*/

		case MUTUAL_INFORMATION_WORST_PLUS_BEST:
		{
			int i,j;
			
			//it will hold the best population in the best_population array, but will create 
			//the distance matrix based on the worst population
			
			int ** worst_population= (int **)malloc(sizeof(int*)*selected_population_size);
			for(i=0;i<selected_population_size;++i)
			{
				worst_population[i]= (int *)malloc(sizeof(int)*array_size);
			}
	
			for(i=0;i<selected_population_size;++i)
			{
				long champion_index;

				switch(tournament_type)
				{
					case SIMPLE_TOURNAMENT:
					{
						//receive the index of the tournament's champion
						champion_index= loser_of_the_simple_tournament(max_participants, population_size);
					}
					break;

					case EXCLUSIVE_TOURNAMENT:
					{
						//receive the index of the tournament's champion
						//champion_index= loser_of_the_exclusive_tournament(max_participants, population_size, i, selected_index_array);
						//printArray(selected_index_array, i);
						printf("Just remind, you are using exclusive tournament with mutual information only worst, something can go wrong!\nThis option was not entirely programmed\n");
					}
					break;

				}

				for(j=0;j<array_size;++j)
				{
				
					worst_population[i][j]= population[champion_index][j];
				
				}
					
			}


			binaryMutualInformationMetric(worst_population, selected_population_size, array_size);
			
			//sum the matrix computed to the matrix of the last computed distance matrix;
			sumBinaryMutualInformationMetric(best_population, selected_population_size, array_size);
			
			for(i=0;i<selected_population_size;++i)
			{
				free(worst_population[i]);
			}
			free(worst_population);

		}
		break;
	}
}

void hphiga::hillClimbing(int* chromossome)
{
	int i;
	float last_fitness;
	float new_fitness;

	for(i=0;i<array_size;i++)
	{
		last_fitness= (*fitness_pointer)(chromossome, generation, array_size);

		if(chromossome[i]==0)
		{
			chromossome[i]=1;

			new_fitness= (*fitness_pointer)(chromossome, generation, array_size);

			if(new_fitness<last_fitness)
			{
				chromossome[i]=0;
			}
		}
		else
		{
			chromossome[i]=0;

			new_fitness= (*fitness_pointer)(chromossome, generation, array_size);

			if(new_fitness<last_fitness)
			{
				chromossome[i]=1;
			}
			
		}
	}
}

void hphiga::printBestFitness(int population_size, float* best_fitness, float* avg_fitness)
{
	int j;

	*best_fitness= (*fitness_pointer)(population[0],generation, array_size);
	best_individual= population[0];

	*avg_fitness= *best_fitness;

	for(j=1;j<population_size;++j)
	{
		float tmp_fitness= (*fitness_pointer)(population[j],generation, array_size);
		if(*best_fitness < tmp_fitness)
		{
			*best_fitness= tmp_fitness;
			best_individual= population[j];
		}
		
		*avg_fitness+= tmp_fitness;
	}

	*avg_fitness= *avg_fitness/population_size;
	this->best_fit=*best_fitness;

	printf("Best Fitness: %.2f\n", *best_fitness);
	printf("Average Fitness: %.2f\n", *avg_fitness);
}

void hphiga::calcBestFitness(int population_size, float* best_fitness, float* avg_fitness)
{
	int j;

	*best_fitness= (*fitness_pointer)(population[0],generation, array_size);
	best_individual= population[0];

	*avg_fitness= *best_fitness;

	for(j=1;j<population_size;++j)
	{
		float tmp_fitness= (*fitness_pointer)(population[j],generation, array_size);
		if(*best_fitness < tmp_fitness)
		{
			*best_fitness= tmp_fitness;
			best_individual= population[j];
		}
		
		*avg_fitness+= tmp_fitness;
	}

	*avg_fitness= *avg_fitness/population_size;
	this->best_fit=*best_fitness;

}

//the best fitness among all participants wins
long hphiga::simple_tournament(int max_participants, int population_size)
{
	int i;
	//long best_index= rand()%population_size;
	int best_index= (int)random.uniform(0,population_size-1);
	float best_fitness= (*fitness_pointer)(population[best_index],generation, array_size);

	for(i=1;i<max_participants;i++)
	{
		//get a random individual
		int new_index= (int)random.uniform(0,population_size-1);
		//long new_index= rand()%population_size;
		float new_fitness= (*fitness_pointer)(population[new_index],generation, array_size);
		
		//test fitness and replace the best_fitness in case it is better
		if(new_fitness > best_fitness)
		{
			best_index= new_index;
			best_fitness= new_fitness;
		}
	}
		

	//printf("best index %ld fitness %.2f\n\n",best_index,best_fitness);
	
	return best_index;
}

//the worst fitness among all participants wins
long hphiga::loser_of_the_simple_tournament(int max_participants, int population_size)
{
	int i;
	//long best_index= rand()%population_size;
	int best_index= (int)random.uniform(0,population_size-1);
	float best_fitness= (*fitness_pointer)(population[best_index],generation, array_size);

	for(i=1;i<max_participants;i++)
	{
		//get a random individual
		int new_index= (int)random.uniform(0,population_size-1);
		//long new_index= rand()%population_size;
		float new_fitness= (*fitness_pointer)(population[new_index],generation, array_size);
		
		//test fitness and replace the best_fitness in case it is worse
		if(new_fitness < best_fitness)
		{
			best_index= new_index;
			best_fitness= new_fitness;
		}
	}
		

	//printf("best index %ld fitness %.2f\n\n",best_index,best_fitness);
	
	return best_index;
}

//the best fitness among all participants wins
long hphiga::exclusive_tournament(int max_participants, int population_size, int selected_number, int* selected_index_array)
{
	int i;
	//long best_index= rand()%population_size;
	int best_index= (int)random.uniform(0,population_size-1);
	while(already_selected(best_index, selected_number, selected_index_array))
	{
		best_index= (int)random.uniform(0,population_size-1);
	}

	//printf("index %d\n",best_index);
	float best_fitness= (*fitness_pointer)(population[best_index],generation, array_size);

	for(i=1;i<max_participants;i++)
	{
		//get a random individual
		int new_index= (int)random.uniform(0,population_size-1);
		while(already_selected(new_index, selected_number, selected_index_array))
		{
			new_index= (int)random.uniform(0,population_size-1);
		}
		//long new_index= rand()%population_size;
		//printf("index %d\n",new_index);
		float new_fitness= (*fitness_pointer)(population[new_index],generation, array_size);
		
		//test fitness and replace the best_fitness in case it is better
		if(new_fitness > best_fitness)
		{
			best_index= new_index;
			best_fitness= new_fitness;
		}
	}
		

	//printf("best index %ld fitness %.2f\n\n",best_index,best_fitness);
	
	selected_index_array[selected_number]=best_index;
	
	return best_index;
}

//the worst fitness among all participants wins
long hphiga::loser_of_the_exclusive_tournament(int max_participants, int population_size, int selected_number, int* selected_index_array)
{
	int i;
	//long best_index= rand()%population_size;
	int best_index= (int)random.uniform(0,population_size-1);
	while(already_selected(best_index, selected_number, selected_index_array))
	{
		best_index= (int)random.uniform(0,population_size-1);
	}

	//printf("index %d\n",best_index);
	float best_fitness= (*fitness_pointer)(population[best_index],generation, array_size);

	for(i=1;i<max_participants;i++)
	{
		//get a random individual
		int new_index= (int)random.uniform(0,population_size-1);
		while(already_selected(new_index, selected_number, selected_index_array))
		{
			new_index= (int)random.uniform(0,population_size-1);
		}
		//long new_index= rand()%population_size;
		//printf("index %d\n",new_index);
		float new_fitness= (*fitness_pointer)(population[new_index],generation, array_size);
		
		//test fitness and replace the best_fitness in case it is worse
		if(new_fitness < best_fitness)
		{
			best_index= new_index;
			best_fitness= new_fitness;
		}
	}
		

	//printf("best index %ld fitness %.2f\n\n",best_index,best_fitness);
	
	selected_index_array[selected_number]=best_index;
	
	return best_index;
}

bool hphiga::already_selected(int index, int selected_number, int* selected_index_array)
{
	int i;

	for(i=0;i<selected_number;i++)
	{
		if(selected_index_array[i]==index)
		{
			//printf("equal\n");
			return true;
		}
	}

	//not selected yet
	return false;
}

void hphiga::printResult()
{
	int i;
	
	printf("Printing the Result:\n");	
			
/*	list<subset*>::iterator tmp_subset;
	for(tmp_subset= subset_list.begin();tmp_subset!=subset_list.end();tmp_subset++)
	{
		createIndividualPart((*tmp_subset), 0);
	}
*/
	for(i=0;i<array_size;i++)
	{
		printf("%d ",i);
	}
	printf("\n");	
	
	for(i=0;i<array_size;i++)
	{
		printf("%d ",best_individual[i]);
	}


	printf("\n");	
	
}

//return the CPC (entropy of the building block)
//an array of indices forming a building block is passed as parameter
//and the number of blocks
/*float hphiga::compressedPopulationComplexity(int *building_block_ids, int blocks, int** population, int population_size)
{
	int i,j,k;

	float cpc=0;
	float log2= 1/log(2);

	//compute the probability of each setting present in the best_population
	for(i=0;i<population_size;i++)
	{
		//if the building block setting was already processed before, 
		//we should disconsider it
		bool repeated_setting=false;
	
		//check if this setting was not already computed
		for(j=0;j<i && repeated_setting==false;j++)
		{

			//consider equal
			repeated_setting=true;

			//check if it is equal
			for(k=0;k<blocks;k++)
			{
				if(population[i][building_block_ids[k]]!=population[j][building_block_ids[k]])
				{
					repeated_setting=false;
					break;
				}
			}
	

		}
			
		//stop this computation if we have already computed the setting
		if(repeated_setting==true)
		{
			continue;
		}

		int counter=1;
		
		//compute probability of this BB setting
		for(j=(i+1);j<population_size;j++)
		{
			//consider equal
			repeated_setting=true;

			//check if it is equal
			for(k=0;k<blocks;k++)
			{
				if(population[i][building_block_ids[k]]!=population[j][building_block_ids[k]])
				{
					repeated_setting=false;
					break;
				}
			}

			if(repeated_setting==true)
			{
				counter++;
			}
						
		}

		float probability= counter/population_size;

		cpc+= - probability*log(probability)*log2;

	}

	return cpc;
	
}
*/

float hphiga::CCC(list<Graph_Node*>* tree_list, int selected_population_size)
{

	int sub_tree_size;

	list<Graph_Node*>::iterator tmp_tree;
		
	float frequency_counter_length= logf(selected_population_size)/logf(2.0);

	float mc=0;
	float cpc=0;

	for(tmp_tree=tree_list->begin();tmp_tree!=tree_list->end(); tmp_tree++)
	{
		//model complexity 
		sub_tree_size=(*tmp_tree)->numberOfLeafNodes();
	
		float number_of_frequency_counters= powf(2,sub_tree_size);

		mc+= number_of_frequency_counters * frequency_counter_length; 
		
	//	printf("frequency %f\n",number_of_frequency_counters);
	//	printf("frequency lenght%f\n",frequency_counter_length);
	//	printf("mc%f\n",mc);


		//compressed population complexity (entropy)

		int indices_size;
		int* indices= (*tmp_tree)->arrayOfLeafIds(&indices_size);

		//printf("ind %d\n",indices_size);
		//printArray(indices, indices_size);

		cpc+= selected_population_size*entropy(indices, indices_size, best_population, selected_population_size);
	//	printf("cpc %f\n",cpc);

	}
		
	//printf("final mc %f\n",mc);
	//printf("final cpc %f\n",cpc);

	return (mc+cpc);
}


bool hphiga::checkStopCondition(int population_size)
{
	float avg_fitness;
	float best_fitness;

	printBestFitness(population_size, &best_fitness, &avg_fitness);

	if(avg_fitness <= best_fitness + 0.01 && avg_fitness >= best_fitness - 0.01)
	{
		//stop evolution, homogeneous population
		return false;
	}
	else
	{	
		//continue evolution
		return true;
	}
}

void hphiga::recursiveCutTreeOnAverageThreshold(float threshold, list<Graph_Node*>* tree_list, Graph_Node* node)
{
	int i;

	for(i=0;i<node->connection_number;i++)
	{
		recursiveCutTreeOnAverageThreshold(threshold, tree_list, node->connection[i]);
		
	}
	
	for(i=0;i<node->connection_number;i++)
	{
		if(threshold < node->connection_weight[i])
		{
			Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
			tree_list->push_front(removed_node);
		}
		
	}

}

void hphiga::recursiveCutTreeAsideFromLeafNodes(float threshold, list<Graph_Node*>* tree_list, Graph_Node* node)
{
	int i;

	for(i=0;i<node->connection_number;i++)
	{
		recursiveCutTreeAsideFromLeafNodes(threshold, tree_list, node->connection[i]);
		
	}
	
	for(i=0;i<node->connection_number;i++)
	{
		//check if it is NOT a leaf node
		if((node->connection[i])->connection_number!=0)
		{
			//check if it should be cut in this part
			if(threshold < node->connection_weight[i])
			{
				Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
				tree_list->push_front(removed_node);
				printf("cut\n");
			}
		}
	}

}

void hphiga::recursiveCutTreeSimple(int focus, list<Graph_Node*>* tree_list, Graph_Node* node)
{
	int i;

	focus--;

	//continue recursive throughout the tree till the focus reach 0 
	for(i=0;i<node->connection_number&&focus>0;i++)
	{
		recursiveCutTreeSimple(focus, tree_list, node->connection[i]);
		
	}

	//when the focus reach 0, cut all subtrees...
	if(focus==0)
	{
		for(i=0;i<node->connection_number;i++)
		{
			Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
			tree_list->push_front(removed_node);
			
		}
	}

}

void hphiga::recursiveSetBuildingBlock(int building_block_id, int* bb, Graph_Node* node)
{
	int i;

	for(i=0;i<node->connection_number;i++)
	{
		recursiveSetBuildingBlock(building_block_id, bb, node->connection[i]);
	}

	//if the node is a variable (a leave in the original tree), lets set the building_block_id 
	//in the building_block
	if(node->id<array_size)
	{
		bb[(int)node->id]= building_block_id;
		//building_block[(int)building_block_id]= node->id;
		//printf("id %d, bb %d\n",(int)node->id, building_block_id);
	}
}

//cut the root_tree passed creating new trees
//and return the number of new trees created
//
//building_block is a chromossome sized variable passed, so that it will be filled in the end 
//with numbers relative to which tree a respective gene is, those trees
//are the well known building blocks
int hphiga::cutTreeOnAverageThreshold(float maximum, float minimum, Graph_Node* root, int* building_block)
{
	//initialize
	list<Graph_Node*> tree_list;

	float threshold= (maximum+minimum)/2;

	printf("threshold %.2f\n",threshold);


	recursiveCutTreeOnAverageThreshold(threshold, &tree_list, root);

	tree_list.push_front(root);

	
	list<Graph_Node*>::iterator tmp_tree;
	int counter=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		recursiveSetBuildingBlock(counter, building_block, *(tmp_tree));
		(*tmp_tree)->deleteTree();
	}
		
	return counter;
}

int hphiga::cutTreeAsideFromLeafNodes(float maximum, float minimum, Graph_Node* root, int* building_block)
{
	//initialize
	list<Graph_Node*> tree_list;

	float threshold= (maximum+minimum)/2;

	printf("threshold %.2f\n",threshold);


	recursiveCutTreeAsideFromLeafNodes(threshold, &tree_list, root);

	tree_list.push_front(root);


	
	list<Graph_Node*>::iterator tmp_tree;
	int counter=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		recursiveSetBuildingBlock(counter, building_block, *(tmp_tree));
		(*tmp_tree)->deleteTree();
	}




	return counter;
}

int hphiga::applyBBFunction(Graph_Node* root, int* building_block)
{
	//initialize
	list<Graph_Node*> tree_list;

	int count=0;
		
	char tmp_filename[9];

	sprintf(tmp_filename,"root.dot");
	root->print(tmp_filename);

	recursiveApplyBBFunction(&tree_list, root, &count);
	
	tree_list.push_front(root);
	
//	int i;
//	for(i=0;i<array_size;i++)
//	{	
///		building_block[i]=-1;
//	}



	list<Graph_Node*>::iterator tmp_tree;
	
	int counter=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		/*char tmp_filename[7];

		sprintf(tmp_filename,"%d.dot",counter);

		(*tmp_tree)->print(tmp_filename);
		*/
		recursiveSetBuildingBlock(counter, building_block, *(tmp_tree));
		(*tmp_tree)->deleteTree();
	}

/*
	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++)
	{
		(*tmp_tree)->print();
		//(*tmp_tree)->deleteTree();
	}
*/		
	return counter;
}

int hphiga::applyLayerFunction(Graph_Node* root, int* building_block)
{
	//initialize
	list<Graph_Node*> tree_list;
		
	int i;
	int root_height= root->treeHeight();
	int count= root_height -1;

	//calculating cut fuction 
	recursiveApplyLayerFunction(&tree_list, root, count);
	//float ccc= CCC(&tree_list, selected_population_size);


	//allocate bbs
//	if(root_height-2>3)
//		number_of_bbs=3;
//	else
		number_of_bbs= root_height-2;
	//number_of_bbs= root_height-2;
	possible_building_blocks=(int**)malloc(sizeof(int*)*(number_of_bbs));
	for(i=0;i<number_of_bbs;i++)
	{
		possible_building_blocks[i]=(int*)malloc(sizeof(int)*array_size);
	}
	
	possible_blocks=(int*)malloc(sizeof(int)*(number_of_bbs));
	//float* cccs=(float*)malloc(sizeof(float)*(number_of_bbs));
	
	//setting building block

	list<Graph_Node*>::iterator tmp_tree;
	
	int counter=0;
	int bbs=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		recursiveSetBuildingBlock(counter, possible_building_blocks[bbs], *(tmp_tree));
	}
	possible_blocks[bbs]=counter;
	//cccs[bbs]=ccc;
	bbs++;
	
	tree_list.clear();



	
//	printf("CCC %f  height %d\n",ccc, root_height);

	count--;

//	float last_ccc=ccc;

	//for(count=2;count<root_height-1;count++)
	for(;count>0;count--)
	{
		//calculating cut fuction 
		recursiveApplyLayerFunction(&tree_list, root, count);

		//ccc= CCC(&tree_list, selected_population_size);

	
		//checking if this building block is better than the others already computed
		int counter=0;

		if(bbs<number_of_bbs)
		{
			//case there is still not enough bbs stored
			for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
			{
				recursiveSetBuildingBlock(counter, possible_building_blocks[bbs], *(tmp_tree));
			}
			possible_blocks[bbs]=counter;
			//cccs[bbs]=ccc;
			bbs++;

		}
		
		tree_list.clear();

	}

	return possible_blocks[0];
}

int hphiga::applyDiscontinuityFunction(Graph_Node* root, int* building_block, int node_to_cut)
{
	//initialize
	list<Graph_Node*> tree_list;
	
	//calculating cut fuction 
	recursiveApplyDiscontinuityFunction(&tree_list, root, node_to_cut);


	//setting building block

	list<Graph_Node*>::iterator tmp_tree;
	int counter=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		recursiveSetBuildingBlock(counter, building_block, *(tmp_tree));
	}

	tree_list.clear();

	return counter;

}

int hphiga::applyLayerFunctionWithCCC(Graph_Node* root, int* building_block)
{
	//initialize
	list<Graph_Node*> tree_list;
		
	int i;
	int root_height= root->treeHeight();
	int count= root_height -1;

	//calculating cut fuction 
	recursiveApplyLayerFunction(&tree_list, root, count);
	float ccc= CCC(&tree_list, selected_population_size);


	//allocate bbs
//	if(root_height-2>3)
//		number_of_bbs=3;
//	else
		number_of_bbs= root_height-2;
	//number_of_bbs= root_height-2;
	possible_building_blocks=(int**)malloc(sizeof(int*)*(number_of_bbs));
	for(i=0;i<number_of_bbs;i++)
	{
		possible_building_blocks[i]=(int*)malloc(sizeof(int)*array_size);
	}
	
	possible_blocks=(int*)malloc(sizeof(int)*(number_of_bbs));
	cccs=(float*)malloc(sizeof(float)*(number_of_bbs));
	
	//setting building block

	list<Graph_Node*>::iterator tmp_tree;
	
	int counter=0;
	int bbs=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		recursiveSetBuildingBlock(counter, possible_building_blocks[bbs], *(tmp_tree));
	}
	possible_blocks[bbs]=counter;
	cccs[bbs]=ccc;
	bbs++;
	
	tree_list.clear();



	
//	printf("CCC %f  height %d\n",ccc, root_height);

	count--;

//	float last_ccc=ccc;

	//for(count=2;count<root_height-1;count++)
	for(;count>0;count--)
	{
		//calculating cut fuction 
		recursiveApplyLayerFunction(&tree_list, root, count);

		ccc= CCC(&tree_list, selected_population_size);

	
		//checking if this building block is better than the others already computed
		int counter=0;

		if(bbs<number_of_bbs)
		{
			//case there is still not enough bbs stored
			for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
			{
				recursiveSetBuildingBlock(counter, possible_building_blocks[bbs], *(tmp_tree));
			}
			possible_blocks[bbs]=counter;
			cccs[bbs]=ccc;
			bbs++;

		}
		/*else
		{
			int j;
			for(j=0;j<bbs;j++)
			{
			//	if(cccs[bbs]>ccc)
				{
					for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
					{
						recursiveSetBuildingBlock(counter, possible_building_blocks[bbs], *(tmp_tree));
					}
					possible_blocks[bbs]=counter;
			//		cccs[bbs]=ccc;

					break;
				}
			}
			
		}
		*/

		/*for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
		{
			recursiveSetBuildingBlock(counter, possible_building_blocks[(count-1)], *(tmp_tree));
		}
		possible_blocks[count-1]=counter;
		*/
		
		tree_list.clear();

		//printf("CCC %f\n",ccc);

//		if(last_ccc<(ccc/10)&&bbs==number_of_bbs)
//			break;
	}

	if(print_cccs)
	{
		int layer=0;
		printf("Printing Layers CCCs from root to leaf:\n");
		printf("layer %d (root): ccc not computed\n",layer);
		layer++;


		for(i=number_of_bbs-1; i>=0;i--)
		{
			printf("layer %d: %.2f\n",layer,cccs[i]);
			layer++;
		}
		printf("layer %d (leaf): ccc not computed\n",layer);

	}
			
//	int j;
//	printf("\n");
//	for(i=0;i<bbs;i++)
//	{
//		printf("ccc %f\n",cccs[i]);
//	}
	
	
	//printing bbs
//	for(i=0;i<number_of_bbs;i++)
//	{
//		printArray(possible_building_blocks[i],array_size);
//		//free(possible_building_blocks[i]);
//	}
	//free(possible_building_blocks);

	//return 0;

//	free(cccs);

	return possible_blocks[0];
}

void hphiga::recursiveApplyLayerFunction(list<Graph_Node*>* tree_list, Graph_Node* node, int counter)
{
	int i;
	
	if(counter<0)
		return;

	counter--;

	for(i=0;i<node->connection_number;i++)
	{
		
		if(counter==0||(node->connection[i])->connection_number==0)
		{	
			//Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
			tree_list->push_back(node->connection[i]);
			
		}
		else
		{
			recursiveApplyLayerFunction(tree_list, node->connection[i], counter);

		}

	}
	
}

void hphiga::recursiveApplyDiscontinuityFunction(list<Graph_Node*>* tree_list, Graph_Node* node, int node_to_cut)
{
	int i;
	
	for(i=0;i<node->connection_number;i++)
	{
		
		if(node->id >= node_to_cut && (node->connection[i])->id < node_to_cut)
		{	
			//Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
			tree_list->push_back(node->connection[i]);
			
		}
		else
		{
			recursiveApplyDiscontinuityFunction(tree_list, node->connection[i], node_to_cut);

		}

	}
	
}

float hphiga::recursiveApplyBBFunction(list<Graph_Node*>* tree_list, Graph_Node* node, int* counter)
{
	int i;

	int sum_counter=0;

	for(i=0;i<node->connection_number;i++)
	{
		float function= recursiveApplyBBFunction(tree_list, node->connection[i], counter);
		
		if(function!=-1 && node->connection_weight[i] > function )
		{	
			Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
			tree_list->push_back(removed_node);
			(*counter)=0;
			
			/*printf("cut %d\n",(int)(node->connection[i])->id);
		
			char tmp_filename[10];

			sprintf(tmp_filename,"%d_s.dot",tree_list->size()-1);

			removed_node->print(tmp_filename);
			*/
		}
		//printf("function %f connection weight %f\n", function, node->connection_weight[i]);

		//set the counter to zero, to not influenciate
		//adjacent paths 
		sum_counter+= (*counter);
		(*counter)=0;

	}
				
	//printf("variable %.2f\n",node->id);
	//printf("counter %d\n", *counter);
	
	//sum all counters in below this node 
	(*counter)+= sum_counter;
	

	//if leaf node, increase counter
	//this counter will be used as the size of the BB being formed
	if(node->connection_number==0)
	{
		(*counter)++;
	}

	
	//for(i=0;i<node->connection_number;i++)
	{
		float function;

		if(*counter!=0)
		{
			function= function_k*1.0/(float)(*counter);
			return function;
		}
		else
		{
			return -1;
		}



		//check if it is NOT a leaf node
		//if((node->connection[i])->connection_number!=0)
		//{
			//check if it should be cut in this part
		//	if(threshold < node->connection_weight[i])
		//	{
		//		Graph_Node* removed_node= node->removeConnectionWithIndex(i);		
		//		tree_list->push_front(removed_node);
		//		printf("cut\n");
		//	}



		//}
	}

}


int hphiga::cutTreeSimple(int focus, Graph_Node* root, int* building_block)
{
	//initialize
	list<Graph_Node*> tree_list;

	tree_list.push_front(root);

	recursiveCutTreeSimple(focus, &tree_list, root);

	
	list<Graph_Node*>::iterator tmp_tree;
	int counter=0;

	for(tmp_tree=tree_list.begin();tmp_tree!=tree_list.end(); tmp_tree++, counter++)
	{
		recursiveSetBuildingBlock(counter, building_block, *(tmp_tree));
	}
		
	return counter;
}
	

//use the "value metric", 
//that is, similar values from different variables will get together in a building block through this metric
void hphiga::valueMetric(int** population, int population_size, int array_size)
{
	int i,j;

	float *distribution=(float *)malloc(sizeof(float)*array_size);

	//create a array with the distribution of the population
	for(j=0;j<array_size;j++)
	{
		float sum=0.0f;

		for(i=0;i<population_size;i++)
		{
			sum+= population[i][j];
		}
		sum/=population_size;
	
		distribution[j]=sum;
	}
	
	int n=array_size;


	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			distance_matrix[i][j]= fabs(distribution[j]-distribution[i])*10;
		}
	}
	



	//cleaning
	free(distribution);
	
}

void hphiga::sumBinaryMutualInformationMetric(int** sample, int sample_size, int array_size)
{
	int i,j;

	float *variable_avg=(float *)malloc(sizeof(float)*array_size);

	//create a array with the distribution of the sample
	for(j=0;j<array_size;j++)
	{
		float sum=0.0f;

		for(i=0;i<sample_size;i++)
		{
			sum+= sample[i][j];
		}
		sum= (float)sum/(float)sample_size;
	
		variable_avg[j]=sum;
	}
	
	int n=array_size;
		

	float log2= 1/log(2);
		
	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			int k;
			float counter=0;
			
			//calculating probability of x=0 and y=0
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]== 0&&sample[k][j]==0)
				{
					counter++;
				}
			}
			float probability00= (float)counter/(float)sample_size;
			
			//calculating probability of x=0 and y=1
			counter=0;
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]==0 && sample[k][j]==1)
				{
					counter++;
				}
			}
			float probability01= (float)counter/(float)sample_size;
			
			//calculating probability of x=1 and y=0
			counter=0;
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]==1 && sample[k][j]==0)
				{
					counter++;
				}
			}
			float probability10= (float)counter/(float)sample_size;
			
			//calculating probability of x=1 and y=0
			counter=0;
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]==1 && sample[k][j]==1)
				{
					counter++;
				}
			}
			float probability11= (float)counter/(float)sample_size;

			//variable_avg is equal to the probability of a random variable to be 1
			
			/*
			
			*/	
	 		/*
			float mutual_information=0;
			if(probability00!=0)
				mutual_information+= probability00*fast_log2(probability00/((1-variable_avg[i])*(1-variable_avg[j]))); 
			if(probability01!=0)
				mutual_information+= probability01*fast_log2(probability01/((1-variable_avg[i])*variable_avg[j]));
			if(probability10!=0)
				mutual_information+= probability10*fast_log2(probability10/(variable_avg[i]*(1-variable_avg[j])));
			if(probability11!=0)
				mutual_information+= probability11*fast_log2(probability11/(variable_avg[i]*variable_avg[j]));

			float joint_entropy=0;
			if(probability00!=0)
				joint_entropy+= -(probability00*fast_log2(probability00));
			if(probability01!=0)
				joint_entropy+= -(probability01*fast_log2(probability01));
			if(probability10!=0)
				joint_entropy+= -(probability10*fast_log2(probability10));
			if(probability11!=0)
				joint_entropy+= -(probability11*fast_log2(probability11));
			*/	

	 		float mutual_information=0;
			float joint_entropy=0;
			
			if(use_fast_log)
			{
			
				mutual_information+= probability00*fast_log2(probability00/((1-variable_avg[i])*(1-variable_avg[j]))); 
				mutual_information+= probability01*fast_log2(probability01/((1-variable_avg[i])*variable_avg[j]));
				mutual_information+= probability10*fast_log2(probability10/(variable_avg[i]*(1-variable_avg[j])));
				mutual_information+= probability11*fast_log2(probability11/(variable_avg[i]*variable_avg[j]));

				joint_entropy+= -(probability00*fast_log2(probability00));
				joint_entropy+= -(probability01*fast_log2(probability01));
				joint_entropy+= -(probability10*fast_log2(probability10));
				joint_entropy+= -(probability11*fast_log2(probability11));
			}	
			else
			{
				if(probability00!=0)
					mutual_information+= probability00*log(probability00/((1-variable_avg[i])*(1-variable_avg[j])))*log2; 
				if(probability01!=0)
					mutual_information+= probability01*log(probability01/((1-variable_avg[i])*variable_avg[j]))*log2;
				if(probability10!=0)
					mutual_information+= probability10*log(probability10/(variable_avg[i]*(1-variable_avg[j])))*log2;
				if(probability11!=0)
					mutual_information+= probability11*log(probability11/(variable_avg[i]*variable_avg[j]))*log2;

				if(probability00!=0)
					joint_entropy+= -(probability00*log(probability00)*log2);
				if(probability01!=0)
					joint_entropy+= -(probability01*log(probability01)*log2);
				if(probability10!=0)
					joint_entropy+= -(probability10*log(probability10)*log2);
				if(probability11!=0)
					joint_entropy+= -(probability11*log(probability11)*log2);

			}
	 		
			
			/*
			if(isnan(joint_entropy))
			{
				printf("joint entropy is nan\n");
				printf("probability 00 %.2f\n",probability00);
				printf("probability 01 %.2f\n",probability01);
				printf("probability 10 %.2f\n",probability10);
				printf("probability 11 %.2f\n",probability11);
				printf("i %d variable_avg %.2f\n",i, variable_avg[i]);
				printf("j %d variable_avg %.2f\n",j, variable_avg[j]);
				exit(1);
			}
			
			if(isnan(mutual_information))
			{
				printf("mutual information is nan\n");
				printf("probability 00 %.2f\n",probability00);
				printf("probability 01 %.2f\n",probability01);
				printf("probability 10 %.2f\n",probability10);
				printf("probability 11 %.2f\n",probability11);
				printf("i %d variable_avg %.2f\n",i, variable_avg[i]);
				printf("j %d variable_avg %.2f\n",j, variable_avg[j]);
				exit(1);
			}
			*/

			distance_matrix[i][j]+= 100*(joint_entropy-mutual_information);
			//distance_matrix[i][j]= 100*(-mutual_information);



			//min_distance+= distance_matrix[i][j];
			//counter_distance++;

		}
	}
			
/*	min_distance/= counter_distance;
	
	//normalize distances
	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			distance_matrix[i][j]-=min_distance;
		}
	}
*/
	


	//cleaning
	free(variable_avg);

}

//use the "mutual information" metric for binary, 
//it is a famous mathematic metric for mutual dependency of variables
//
//as a result, the distance_matrix will be set for further use
//with neighbor_joining
void hphiga::binaryMutualInformationMetric(int** sample, int sample_size, int array_size)
{
	int i,j;

	float *variable_avg=(float *)malloc(sizeof(float)*array_size);

	//create a array with the distribution of the sample
	for(j=0;j<array_size;j++)
	{
		float sum=0.0f;

		for(i=0;i<sample_size;i++)
		{
			sum+= sample[i][j];
		}
		sum= (float)sum/(float)sample_size;
	
		variable_avg[j]=sum;
	}
	
	int n=array_size;
		

	float log2= 1/log(2);
		
	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			int k;
			float counter=0;
			
			//calculating probability of x=0 and y=0
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]== 0&&sample[k][j]==0)
				{
					counter++;
				}
			}
			float probability00= (float)counter/(float)sample_size;
			
			//calculating probability of x=0 and y=1
			counter=0;
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]==0 && sample[k][j]==1)
				{
					counter++;
				}
			}
			float probability01= (float)counter/(float)sample_size;
			
			//calculating probability of x=1 and y=0
			counter=0;
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]==1 && sample[k][j]==0)
				{
					counter++;
				}
			}
			float probability10= (float)counter/(float)sample_size;
			
			//calculating probability of x=1 and y=0
			counter=0;
			for(k=0;k<sample_size;k++)
			{
				if(sample[k][i]==1 && sample[k][j]==1)
				{
					counter++;
				}
			}
			float probability11= (float)counter/(float)sample_size;

			//variable_avg is equal to the probability of a random variable to be 1
			
			/*
			
			*/	
	 		/*
			float mutual_information=0;
			if(probability00!=0)
				mutual_information+= probability00*fast_log2(probability00/((1-variable_avg[i])*(1-variable_avg[j]))); 
			if(probability01!=0)
				mutual_information+= probability01*fast_log2(probability01/((1-variable_avg[i])*variable_avg[j]));
			if(probability10!=0)
				mutual_information+= probability10*fast_log2(probability10/(variable_avg[i]*(1-variable_avg[j])));
			if(probability11!=0)
				mutual_information+= probability11*fast_log2(probability11/(variable_avg[i]*variable_avg[j]));

			float joint_entropy=0;
			if(probability00!=0)
				joint_entropy+= -(probability00*fast_log2(probability00));
			if(probability01!=0)
				joint_entropy+= -(probability01*fast_log2(probability01));
			if(probability10!=0)
				joint_entropy+= -(probability10*fast_log2(probability10));
			if(probability11!=0)
				joint_entropy+= -(probability11*fast_log2(probability11));
			*/	

	 		float mutual_information=0;
			float joint_entropy=0;
			
			if(use_fast_log)
			{
			
				mutual_information+= probability00*fast_log2(probability00/((1-variable_avg[i])*(1-variable_avg[j]))); 
				mutual_information+= probability01*fast_log2(probability01/((1-variable_avg[i])*variable_avg[j]));
				mutual_information+= probability10*fast_log2(probability10/(variable_avg[i]*(1-variable_avg[j])));
				mutual_information+= probability11*fast_log2(probability11/(variable_avg[i]*variable_avg[j]));

				joint_entropy+= -(probability00*fast_log2(probability00));
				joint_entropy+= -(probability01*fast_log2(probability01));
				joint_entropy+= -(probability10*fast_log2(probability10));
				joint_entropy+= -(probability11*fast_log2(probability11));
			}	
			else
			{
				if(probability00!=0)
					mutual_information+= probability00*log(probability00/((1-variable_avg[i])*(1-variable_avg[j])))*log2; 
				if(probability01!=0)
					mutual_information+= probability01*log(probability01/((1-variable_avg[i])*variable_avg[j]))*log2;
				if(probability10!=0)
					mutual_information+= probability10*log(probability10/(variable_avg[i]*(1-variable_avg[j])))*log2;
				if(probability11!=0)
					mutual_information+= probability11*log(probability11/(variable_avg[i]*variable_avg[j]))*log2;

				if(probability00!=0)
					joint_entropy+= -(probability00*log(probability00)*log2);
				if(probability01!=0)
					joint_entropy+= -(probability01*log(probability01)*log2);
				if(probability10!=0)
					joint_entropy+= -(probability10*log(probability10)*log2);
				if(probability11!=0)
					joint_entropy+= -(probability11*log(probability11)*log2);

			}
	 		
			
			/*
			if(isnan(joint_entropy))
			{
				printf("joint entropy is nan\n");
				printf("probability 00 %.2f\n",probability00);
				printf("probability 01 %.2f\n",probability01);
				printf("probability 10 %.2f\n",probability10);
				printf("probability 11 %.2f\n",probability11);
				printf("i %d variable_avg %.2f\n",i, variable_avg[i]);
				printf("j %d variable_avg %.2f\n",j, variable_avg[j]);
				exit(1);
			}
			
			if(isnan(mutual_information))
			{
				printf("mutual information is nan\n");
				printf("probability 00 %.2f\n",probability00);
				printf("probability 01 %.2f\n",probability01);
				printf("probability 10 %.2f\n",probability10);
				printf("probability 11 %.2f\n",probability11);
				printf("i %d variable_avg %.2f\n",i, variable_avg[i]);
				printf("j %d variable_avg %.2f\n",j, variable_avg[j]);
				exit(1);
			}
			*/

			distance_matrix[i][j]= 100*(joint_entropy-mutual_information);
			//distance_matrix[i][j]= 100*(-mutual_information);



			//min_distance+= distance_matrix[i][j];
			//counter_distance++;

		}
	}
			
/*	min_distance/= counter_distance;
	
	//normalize distances
	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			distance_matrix[i][j]-=min_distance;
		}
	}
*/
	


	//cleaning
	free(variable_avg);

}

//use the "value metric", 
//that is, similar values from different variables will get together in a building block through this metric
void hphiga::mixMetric(int** population, int population_size, int array_size)
{
	int i,j;

	int n=array_size;

	binaryMutualInformationMetric(population, population_size, array_size);

	normalizeDistanceMatrix();
	
	float **blend_distance_matrix=(float **)malloc(sizeof(float*)*array_size);
	for(i=0;i<array_size;i++)
	{
		blend_distance_matrix[i]= (float*)malloc(sizeof(float)*array_size);
	}

	//copying the distance matrix to a temporary matrix
	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			blend_distance_matrix[i][j]= distance_matrix[i][j];
		}
	}
	
	valueMetric(best_population, selected_population_size, array_size);

	normalizeDistanceMatrix();
	
	//blending the distance matrix to a temporary matrix
	for(i=0;i<n;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			blend_distance_matrix[i][j]+= distance_matrix[i][j];
			blend_distance_matrix[i][j]/= 2;
			distance_matrix[i][j]= blend_distance_matrix[i][j];
			
		}
	}

	//cleaning
	for(i=0;i<array_size;i++)
	{
		free(blend_distance_matrix[i]);
	}
	free(blend_distance_matrix);
	
}
	
void hphiga::normalizeDistanceMatrix()
{
	int i,j;
	float maximum, minimum;

	maximum= distance_matrix[0][0];
	minimum= distance_matrix[0][0];

	//find the maximum and minimum distances
	for(i=0;i<array_size;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			if(minimum>distance_matrix[i][j])
				minimum= distance_matrix[i][j];
			
			if(maximum<distance_matrix[i][j])
				maximum= distance_matrix[i][j];
		}
	}
	

	//normalize distances
	for(i=0;i<array_size;i++)
	{
		//sum only the distances below the main diagonal in the matrix
		//The @ are the numbers that would be summed in the example:
		//[ x      ]		
		//[ @ x	   ]
		//[ @ @ x  ]
		//[ @ @ @ x]
		
		for(j=0;j<i;j++)
		{
			distance_matrix[i][j]= 10*(distance_matrix[i][j] - minimum)/(maximum-minimum) ;
		}
	}
}

float hphiga::fast_log2(float value)
{
	if(value>100.0f)
	{
		return 5.0f;
	}


	return log_hash_table[(int)(value*table_size/100.0f)];
}

//the table size defines the accuracy of the function
void hphiga::prepare_log(float table_size)
{
	int i;
	
	this->table_size= table_size;
	log_hash_table=(float*)malloc(table_size*sizeof(float));

	float log2= 1/log(2);
	
	//undefined log, it will be set to 0
	log_hash_table[0]= 0;

	for(i=1;i<table_size;i++)
	{
		log_hash_table[i]= log((float)i*(100.0f/table_size))*log2;
	}
}


void hphiga::printSimpleResult()
{
	printf("\n");

	printf("generation: %d\n",generation);
	printf("fitness: %.2f\n",best_fit);
}

int* hphiga::generateAllPossibilities(int* building_block, int bbs)
{
	int i, j,k;
	
	int* bb_index= (int*)malloc(sizeof(int)*array_size);
	int* sample= (int*)calloc(array_size,sizeof(int));
	int* best_solution= (int*)malloc(sizeof(int)*array_size);

	printArray(building_block, array_size);

	float best_fitness;
	
	//for all building blocks
	for(j=0; j<bbs ;j++)
	{
		//printf("bb %d\n",j);

		int bb_size=0;
		//count the number of variables in this bb and store their index in the bb_index
		for(i=0;i<array_size;i++)
		{	
			if(building_block[i]==j)
			{
				bb_index[bb_size]= i;			
				bb_size++;
			}
		}
	
		//a fast way to do pow(2,bb_size)
		int possibilities= 1<<bb_size;

		//printf("sampling and finding the best solution\n");

		//---------Sampling and storing the best one in the best_solution array-------
		sample= (int*)memset(sample,0,array_size*sizeof(int));
		//consider the first sample to be the best
		i=0;
		for(k=0;k<bb_size;k++)
		{
			unsigned int mask= 1<<k;
			//printf("%d ",(mask&i)>>j);

			//the sample receive in the correct index position a possibility
			sample[bb_index[k]]=mask&i>>k;
		}

		for(k=0;k<bb_size;k++)
		{
			//store best solution
			best_solution[bb_index[k]] = sample[bb_index[k]];
		}
		best_fitness= (*fitness_pointer)(sample, 0, array_size);

		//compare the first sample with the other
		for(i=1;i<possibilities;i++)
		{
			for(k=0;k<bb_size;k++)
			{
				unsigned int mask= 1<<k;
				//printf("%d ",(mask&i)>>j);

				//the sample receive in the correct index position a possibility
				sample[bb_index[k]]=(mask&i)>>k;
			}
	
			float fitness= (*fitness_pointer)(sample, 0, array_size);
			if(fitness > best_fitness)
			{
				for(k=0;k<bb_size;k++)
				{
					//store best solution
					best_solution[bb_index[k]] = sample[bb_index[k]];
				}
				best_fitness= fitness;
			}

			//printf("\n");
		}

		//printing
		/*
		printf("print:\n");
		for(k=0;k<bb_size;k++)
		{
			//store best solution
			printf("%d,%d ", bb_index[k],best_solution[bb_index[k]]);
		}
		printf("\n");
		*/

			
	}


	
	free(sample);
	free(bb_index);

	return best_solution;

}
